package br.unisinos.aidk.searcher;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Random;

import br.unisinos.aidk.graph.Node;
import br.unisinos.aidk.graph.Queue;

public class BestFirstSearch<V> implements SearchStrategy<V> {

	public static final Random RND = new Random();

	protected Comparator<V> cmp;
	
	@Override
	public boolean apply(Queue<Node<V>> queue, LinkedList<Node<V>> nodes) {
	
		//sort(queue.getArray(V), cmp);
		
		//Collections.sort()
		return true;
	}

	private void swap(V[] array, int i, int j) {
        V tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
	
	private int partition(V[] array, int begin, int end, Comparator<V> cmp) {
		int index = begin + RND.nextInt(end - begin + 1);
		V pivot = array[index];
		swap(array, index, end);
		for (int i = index = begin; i < end; ++i) {
			if (cmp.compare(array[i + 1], pivot) <= 0) {
				swap(array, index++, i);
			}
		}
		swap(array, index, end);
		return (index);
	}

	private void qsort(V[] array, int begin, int end, Comparator<V> cmp) {
		if (end > begin) {
			int index = partition(array, begin, end, cmp);
			qsort(array, begin, index, cmp);
			qsort(array, index, end, cmp);
		}
	}

	private void sort(V[] array, Comparator<V> cmp) {
		qsort(array, 0, array.length - 1, cmp);
	}

}
